#ifndef RB_TREE_H
#define RB_TREE_H

/* 仿函数，形态是一个类，但是行为上是一个函数。没有data */

template <class Arg, class Result>
struct unary_function{
    typedef Arg argument_type;
    typedef Result result_type;
};

template<class T>// identity 的数学含义是证同性函数，即不做修改，保持原值。  identity n. 身份；同一性
struct identity : public unary_function<T,T> {
    const T& operator()(const T& x) const {return x;}
};

template <class Arg1, class Arg2, class Result>
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};

template <class T>
struct less : public binary_function<T, T, bool > {
    bool operator() (const T& x, const T& y)   { return x < y;}
};

template <class Key,
          class Value,      //此处的Value 是 key+data ，封装起来的pair。也可以将key 当做 data，那体现出的容器就是Set
          class KeyOfValue, //如何从value 中拿到key
          class Compare,    //排序比大小的方式
          class Alloc = alloc>
class rb_tree {
protected:
    typedef __rb_tree_node<Value> rb_tree_node;
public:
    typedef rb_tree_node* link_type;
    typedef Value value_type;
    typedef const value_type* const_pointer;
    typedef value_type* pointer;
    typedef size_t size_type;
    typedef value_type& reference;
    typedef const value_type& const_reference;


    typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
    typedef _Rb_tree_iterator<value_type, const_reference, const_pointer>
            const_iterator;
protected:
    size_type node_count;
    link_type header;
    Compare key_compare;        //key 的大小比较规则：应该是一个函数对象，即仿函数
};



#endif // RB_TREE_H
